package com.demo.jzoffer2;

/**
 * @author gy
 * @date 2022/11/15
 */
public class Test1116_01 {
    /**
     * 青蛙跳台阶问题（动态规划，）
     * 设跳上 n  级台阶有 f(n)种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。
     * 当为 1级台阶： 剩 n−1个台阶，此情况共有 f(n−1) 种跳法；
     * 当为 2级台阶： 剩 n−2个台阶，此情况共有 f(n−2) 种跳法。
     *  f(n)=f(n−1)+f(n−2)
     *  青蛙跳台阶问题： f(0)=1 , f(1)=1 , f(2)=2 ；
     *  斐波那契数列问题： f(0)=0, f(1)=1, f(2)=1
     * @param n
     * @return
     */
    public int numWays(int n) {
        int a = 1 , b = 1, sum;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}
